package com.localking.algorithm.leetcode.array.string

/**
 * Implement strStr().
 * Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
 *
 * Example 1:
 * Input: haystack = "hello", needle = "ll"
 * Output: 2
 *
 * Example 2:
 * Input: haystack = "aaaaa", needle = "bba"
 * Output: -1
 *
 * Clarification:
 * What should we return when needle is an empty string? This is a great question to ask during an interview.
 * For the purpose of this problem, we will return 0 when needle is an empty string, This is consistent to C's strstr() and Java's indexOf()
 *
 * @author jinbo
 */
object StrStr {
  def main(args: Array[String]): Unit = {
    val haystack = "mississippi"
    val needle = "issip"
    println(strStr(haystack, needle))
  }

  def strStr(haystack: String, needle: String): Int = {
    val haystackSize = haystack.length
    val needleSize = needle.length
    if(needleSize > haystackSize) {
      return -1
    }
    val index = needleSize match {
      case 0 => 0
      case _ => {
        import util.control.Breaks._
        (0 to (haystackSize - needleSize)).foreach(i => {
          breakable {
            for(j <- 0 until needleSize) {
              if(haystack(i + j) != needle(j)) {
                break
              }
            }
            return i
          }
        })
      }
        -1
    }
    index
  }
}
